package huaweiod.first;

import java.util.HashMap;
import java.util.Scanner;

/**
 * 华为机试真题 Java 实现【单向链表中间节点】【2022.11 Q4新题】
 *
 * @author yujiafan
 * @version 1.0.0
 * @create 2023-06-21
 */
public class A_2023_06_LinkedMidNode {
    // 节点定义
    public static class ListNode {
        public int value;
        public int next;

        public ListNode(int value, int next) {
            this.value = value;
            this.next = next;
        }
    }

    public static void main(String[] args) {
        // 处理输入
        Scanner in = new Scanner(System.in);
        String head_node_str = in.nextLine();
        String[] head_info = head_node_str.split(" ");
        int head_addr = Integer.valueOf(head_info[0]);
        int count = Integer.valueOf(head_info[1]);

        HashMap<Integer, ListNode> node_info = new HashMap<Integer, ListNode>();
        for (int i=0;i<count;i++) {
            String node_str = in.nextLine();
            String[] node_list_info = node_str.split(" ");
            int addr = Integer.valueOf(node_list_info[0]);
            int val = Integer.valueOf(node_list_info[1]);
            int next = Integer.valueOf(node_list_info[2]);
            ListNode temp_node = new ListNode(val, next);
            node_info.put(addr, temp_node);
        }
        // 逻辑
        ListNode head = node_info.get(head_addr);
        ListNode slow = head;
        ListNode fast = head;
        while (fast.next != -1 && node_info.get(fast.next).next != -1) {
            slow = node_info.get(slow.next);
            fast = node_info.get(node_info.get(fast.next).next);
        }
        if(fast.next != -1) {
            slow = node_info.get(slow.next);
        }
        System.out.println(slow.value);
    }
}
